package 剑指offer;

public class _13机器人的活动范围 {
    int res = 0;
    public int movingCount(int m, int n, int k) {
        int[][] nums = new int[m][n];
        dfs(0,0,m,n,k,nums);
        return res;
    }
    public void dfs(int i, int j, int m, int n, int k,int[][] nums){
        if(sum(i) +  sum(j) > k || i < 0 || i >= m || j < 0 || j >= n || nums[i][j] == 1){
            return ;
        }
        nums[i][j] = 1;
        res++;
        dfs(i + 1,j,m,n,k,nums);
        dfs(i,j + 1,m,n,k,nums);

    }
    public int sum(int num){
        int sum = 0;
        while(num != 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}
